166E - Tetrahedron - CodeForces Solution

/**
  * Create: Thursday 2023-03-02-00.42.59 GMT+7
  * Title : E. Tetrahedron
  * Author:
*****/


#include <bits/stdc++.h>

using namespace std;

#ifndef   MY_TEMPLATE
template <typename T>                           ostream& operator << (ostream& os, const stack                 <T>         &stack_)                  {os <<   "[";     int n = (int) stack_.size();      vector <T> archive (n);    stack <T>                              stackCopy_ (stack_);   for (int i=0; i<n; ++i) {archive[stackCopy_.size()-1]=stackCopy_.top();       stackCopy_.pop();}     if (!archive.empty())      {for (auto it=archive.begin(); it!=archive.end()-1; ++it)    {os <<*it <<", ";}     os <<archive.back();}     os <<" ";     return os;}
template <typename T>                           ostream& operator << (ostream& os, const queue                 <T>         &queue_)                  {os << "->[";     int n = (int) queue_.size();      vector <T> archive (n);    queue <T>                              queueCopy_ (queue_);   for (int i=0; i<n; ++i) {archive[queueCopy_.size()-1]=queueCopy_ .front();    queueCopy_.pop();}     if (!archive.empty())      {for (auto it=archive.begin(); it!=archive.end()-1; ++it)    {os <<*it <<", ";}     os <<archive.back();}     os <<" ";     return os;}
template <typename T>                           ostream& operator << (ostream& os, const priority_queue        <T,vector<T>,greater<T>>&Queue_)      {os <<   "[";     int n = (int) Queue_.size();      vector <T> archive (n);    priority_queue<T,vector<T>,greater<T>> QueueCopy_ (Queue_);   for (int i=0; i<n; ++i) {archive[QueueCopy_.size()-1]=QueueCopy_.top();       QueueCopy_.pop();}     if (!archive.empty())      {for (auto it=archive.begin(); it!=archive.end()-1; ++it)    {os <<*it <<", ";}     os <<archive.back();}     os <<" ";     return os;}
template <typename T>                           ostream& operator << (ostream& os, const priority_queue        <T>         &Queue_)                  {os <<   "[";     int n = (int) Queue_.size();      vector <T> archive (n);    priority_queue<T>                      QueueCopy_ (Queue_);   for (int i=0; i<n; ++i) {archive[QueueCopy_.size()-1]=QueueCopy_.top();       QueueCopy_.pop();}     if (!archive.empty())      {for (auto it=archive.begin(); it!=archive.end()-1; ++it)    {os <<*it <<", ";}     os <<archive.back();}     os <<" ";     return os;}
template <typename T>                           ostream& operator << (ostream& os, const vector                <T>         &vector_)                 {os <<   "[";     if (!vector_  .empty())           {for (auto it = vector_  .begin(), i=0; i< (int) vector_   .size()-1; ++i, ++it)         {os <<*it <<", ";}     os << * (vector_   .rbegin());}     os << "]";     return os;}
template <typename T>                           ostream& operator << (ostream& os, const deque                 <T>         &deque_)                  {os <<   "[";     if (!deque_   .empty())           {for (auto it = deque_   .begin(), i=0; i< (int) deque_    .size()-1; ++i, ++it)         {os <<*it <<", ";}     os << * (deque_    .rbegin());}     os << "]";     return os;}
template <typename T>                           ostream& operator << (ostream& os, const set                   <T>         &set_)                    {os <<   "[";     if (!set_     .empty())           {for (auto it = set_     .begin(), i=0; i< (int) set_      .size()-1; ++i, ++it)         {os <<*it <<", ";}     os << * (set_      .rbegin());}     os << "]";     return os;}
template <typename T>                           ostream& operator << (ostream& os, const multiset              <T>         &multiSet_)               {os <<   "[";     if (!multiSet_.empty())           {for (auto it = multiSet_.begin(), i=0; i< (int) multiSet_ .size()-1; ++i, ++it)         {os <<*it <<", ";}     os << * (multiSet_ .rbegin());}     os << "]";     return os;}
template <typename T, typename _>               ostream& operator << (ostream& os, const map                   <T, _>      &map_)                    {os <<   "[";     if (!map_     .empty())           {for (auto it = map_     .begin(), i=0; i< (int) map_      .size()-1; ++i, ++it)         {os <<*it <<", ";}     os << * (map_      .rbegin());}     os << "]";     return os;}
template <typename T, typename _>               ostream& operator << (ostream& os, const multimap              <T, _>      &multiMap_)               {os <<   "[";     if (!multiMap_.empty())           {for (auto it = multiMap_.begin(), i=0; i< (int) multiMap_ .size()-1; ++i, ++it)         {os <<*it <<", ";}     os << * (multiMap_ .rbegin());}     os << "]";     return os;}
template <typename T, typename _>               ostream& operator << (ostream& os, const pair                  <T, _>      &pair_)                   {os <<   "{";                                                                                                                                {os <<pair_.first;     os <<":";   os <<pair_.second;}     os << "}";     return os;}
template <typename T>                           void     quick_debug (ostream& os, const char *name,           const T     &value)                   {os <<"[DEBUG]"   << name <<" = " <<value <<endl;};
template <typename T, typename... Args>         void     quick_debug (ostream& os, const char *name,           const T     &value, Args&&... args)   {os <<"[DEBUG]";  while (*name != ',')    {os << *name++;}     os << " = " << value << endl;    quick_debug (os, name + 1, args...);};
#define  hien(...)                              quick_debug(cerr, " " #__VA_ARGS__, __VA_ARGS__)
#define  endl                                   '\n'
#endif


int main() {
   ios_base::sync_with_stdio (0); cin.tie (0);

   #define trying_to_make_a_lot_of_mistakes_when_allowed
   #define trying_to_read_a_lot_of_editorials_when_allowed
   #define int long long


   goto Source;
   Source: https://oeis.org/search?q=3+6+21+60+183+546+1641+4920+14763+44286&sort=&language=english&go=Search


   int n; cin >> n;

   function<int(int,int,int)>
   powMod = [&](int base, int exponent, int mod){
      int res=1;

      for( ;exponent; ){
         if(exponent&1){
            res*=base;
            res%=mod;
         }

         base*=base;
         base%=mod;
         exponent>>=1;
      }

      return res;
   };

   const int mod=1e9+7;
   int ans=(powMod(3, n, mod)+(n%2==1?-1LL:1LL)*3)*powMod(4, mod-2, mod);
   ans%=mod;

   cout <<ans <<endl;



















   return 0;
}